package com.justnow.offer;

import java.util.LinkedList;

/**
 * @author justnow
 * Created on 2020-09-21
 * Description
 *
 * https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/solution/hua-dong-chuang-kou-zui-da-zhi-3chong-jie-jue-fang/
 * https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/solution/java-dan-diao-shuang-xiang-lian-biao-hua-tu-xiang-/
 */



public class Solution63 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        //边界条件的判断
        if (nums == null || k <= 0) {
            return new int[0];
        }
        int index = 0;
        int[] res = new int[nums.length - k + 1];

        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            // 在队列不为空的情况下，如果队列尾部的元素要比当前的元素小，或等于当前的元素
            // 那么为了维持从大到下的原则，让尾部元素弹出，直到不符合while的条件为止，此时继续添加，
            // 可以维持队列单调递减
            while (!queue.isEmpty() && nums[queue.peekFirst()] <= nums[i]) {
                queue.pollLast();
            }
            queue.addLast(i);
            //加入i=3，k = 2，如果i-k为1，即表明i为3时（i从零开始），如果队首为下标1，那么此时滑动窗口已经划过了，下标为1的元素了。
            //需要将这个最大的值给删除掉。
            if (queue.peekFirst() == (i - k)) {
                queue.pollFirst();
            }
            //当窗口的长度大于等于k的时候，将队头的内容放到结果集合中
            if (i >= (k - 1)) {
                res[index++] = nums[queue.peekFirst()];
            }
        }
        return res;
    }
}
